#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2019 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""
树的最长路径/diameter 应用: 在工程中求critical path(最短工期)
"""

class Node:
    def __init__(self, value, left=None, left_edge=0, right=None, right_edge=0):
        self.value = value
        self.left  = left
        self.right = right
        self.left_edge  = left_edge
        self.right_edge = right_edge

def build():
    ll = Node(4)
    lr = Node(5)

    rl = Node(6)
    rr = Node(7)


    l = Node(3, ll, 100, lr, 12)
    r = Node(4, rl, 200, rr, 107)

    return Node(1, l, 2, r, 2)


height_memory = {}           # node : height
diameter_memory = {}        # node as root : diameter


def tree_diameter(tree_root):
    tree_diameter_rec(tree_root)

def tree_diameter_rec(node):
    if node is None:
        return 0

    key = id(node)
    dia = diameter_memory.get(key)
    if dia:
        return dia

    dia = max(
        tree_diameter_rec(node.left),
        tree_diameter_rec(node.right),
        max_hight_of_node(node.left) + max_hight_of_node(node.right) + node.left_edge + node.right_edge
    )

    diameter_memory[key] = dia

    return dia

def max_hight_of_node(node):
    if node is None:
        return 0

    key = id(node)

    max_height = height_memory.get(key)
    if max_height:
        return max_height

    max_height = max(
        node.left_edge + max_hight_of_node(node.left),
        node.right_edge + max_hight_of_node(node.right),
    )

    height_memory[key] = max_height
    return max_height


def test():
    tree_root = build()
    v = tree_diameter_rec(tree_root)
    print(v)


def main():
    print("start main")
    test()

if __name__ == "__main__":
    main()
